package com.jingzhongbao.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/**
 * 1、两数之和
 * 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
 * 你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
 * 给定 nums = [2, 7, 11, 15], target = 9
 * 因为 nums[0] + nums[1] = 2 + 7 = 9
 * 所以返回 [0, 1]
 * **/
public class Code1 {
	public static void main(String[] args) {
		int[] nums = {2, 7, 9, 11};
		String result = Arrays.toString(towNums2(nums, 12));
		System.out.println(result);
	}
	/**
	 * 解法一 两次遍哈希表
	 * 
	 * **/
	public static int[] towNums1(int[] nums, int target) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < nums.length; i++) {
			map.put(nums[i], i);
		}
		for (int i = 0; i < nums.length; i++) {
			int complement = target - nums[i];
			if (map.containsKey(complement) && map.get(complement) != i) {
				return new int[]{map.get(complement), i};
			}
		}
		throw new IllegalArgumentException("No two sum solution");
	}
	/**
	 * 解法二 一次遍哈希表
	 * 
	 * **/
	public static int[] towNums2(int[] nums, int target) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < nums.length; i++) {
			int complement = target - nums[i];
			if (map.containsKey(complement)) {
				return new int[]{map.get(complement), i};
			}
			map.put(nums[i], i);
		}
		throw new IllegalArgumentException("No two sum solution");
	}
}
